class Solution
{
public:
    int quick_sort(vector<int> &nums, int left, int right, int k)
    {
        // printf("left:%d, right:%d, k:%d\n", left, right, k);
        int random = rand() % (right - left + 1) + left;
        swap(nums[left], nums[random]);
        // printf("key:%d\n", nums[left]);
        int lend = left + 1, rhead = right;
        for (int i = left + 1; i <= rhead; ++i)
        {
            while (i <= rhead && nums[i] < nums[left])
                swap(nums[i], nums[rhead--]);
            if (nums[i] > nums[left])
                swap(nums[i], nums[lend++]);
        }
        swap(nums[left], nums[lend - 1]);
        // for(auto e: nums) cout << e << ' ';
        // cout << endl;
        // printf("lend:%d, rhead:%d\n",lend, rhead);
        if (k >= lend && k <= rhead + 1)
            return nums[lend - 1];
        else if (k < lend)
            return quick_sort(nums, left, lend - 1, k);
        else
            return quick_sort(nums, rhead + 1, right, k);
    }
    int findKthLargest(vector<int> &nums, int k)
    {
        srand(time(NULL));
        return quick_sort(nums, 0, nums.size() - 1, k);
    }
};